#include "matrices.h"
#include <math.h>

Matrices::Matrices(int hauteur, int largeur){
    this->hauteur   = hauteur;
    this->largeur   = largeur;

    this->matrice   = new int* [hauteur];
    for ( int i=0 ; i < hauteur ; i++){
        this->matrice[i] = new int [largeur];
    }
}
Matrices::~Matrices(){
    for ( int i=0 ; i < this->hauteur ; i++){
        delete this->matrice [i];
    }
    delete this->matrice;
}

void Matrices::setValeurDansCase(int i, int j, int valeur){
    this->matrice[i][j] = valeur;
}

void Matrices::remplirMatriceDe(int valeur){
    for(int i=0; i<this->hauteur; i++){
        for(int j=0; j<this->largeur; j++){
            this->matrice[i][j] = valeur;
        }
    }
}

int Matrices::getValeurDansCase(int i, int j){
    return this->matrice[i][j];
}

int Matrices::getHauteur(){
    return this->hauteur;
}

int Matrices::getLargeur(){
    return this->largeur;
}

int Matrices::getSommeCoef(){
    int somme   = 0;
    for(int i=0; i<this->hauteur; i++){
        for(int j=0; j<this->largeur; j++){
            somme   += this->matrice[i][j];
        }
    }

    if(somme == 0){ somme = 1; }

    return somme;
}

bool Matrices::isPositionValide(int i, int j){
    return i>=0 && j>=0
            && i<this->hauteur && j<this->largeur;
}


/****************** STATIC *******************/

void Matrices::convolution(QImage * image, Matrices * noyau, double sommeCoef){

    //copie de l'image
    QImage* copy = new QImage(image->copy());
    // les rayons du noyeau
    int rayonHauteur    = (noyau->getHauteur() -1) /2;
    int rayonLargeur    = (noyau->getLargeur() -1) /2;

    // la normalisation
    if(sommeCoef == 0){
        sommeCoef   = noyau->getSommeCoef();
        if(sommeCoef == 0){
            sommeCoef = 1;
        }
    }
    QRgb couleur;
    int coefTmpRouge, coefTmpVert, coefTmpBleu, coefTmpAlpha;
    int tmp;

    // on arrive sur les derniers pixels valides
    int h   = image->height() - rayonHauteur;
    int l   = image->width() - rayonLargeur;

    // puis on boucle
    for(int i=rayonHauteur; i<h; i++){
        for(int j=rayonLargeur; j<l; j++){

            coefTmpRouge    = 0;
            coefTmpVert     = 0;
            coefTmpBleu     = 0;
            coefTmpAlpha    = 0;

            for(int ii = 0; ii < noyau->getHauteur(); ii++){
                for(int jj = 0; jj < noyau->getLargeur(); jj++){
                    couleur = copy->pixel(jj + j - rayonLargeur, ii + i - rayonHauteur);
                    tmp     = noyau->getValeurDansCase(ii, jj);

                    coefTmpRouge    += qRed(couleur) * tmp;
                    coefTmpVert     += qGreen(couleur) * tmp;
                    coefTmpBleu     += qBlue(couleur) * tmp;
                    coefTmpAlpha    += qAlpha(couleur) * tmp;
                }
            }

            coefTmpRouge    = coefTmpRouge/sommeCoef;
            coefTmpVert     = coefTmpVert/sommeCoef;
            coefTmpBleu     = coefTmpBleu/sommeCoef;
            coefTmpAlpha    = coefTmpAlpha/sommeCoef;

            coefTmpRouge    = std::min(255, std::max(0, coefTmpRouge));
            coefTmpVert     = std::min(255, std::max(0, coefTmpVert));
            coefTmpBleu     = std::min(255, std::max(0, coefTmpBleu));
            coefTmpAlpha    = std::min(255, std::max(0, coefTmpAlpha));

            image->setPixel(j, i, qRgba(coefTmpRouge, coefTmpVert, coefTmpBleu, coefTmpAlpha));
        }
    }
    delete copy;
}

void Matrices::convolutionMedianne(QImage * image){
    int tableauRouge[9];
    int tableauVert[9];
    int tableauBleu[9];
    int tableauAlpha[9];

    int h   = image->height() - 1;
    int l   = image->width() - 1;

    QRgb couleur;
    int coefTmpRouge, coefTmpVert, coefTmpBleu, coefTmpAlpha;

    QImage* copy = new QImage(image->copy());

    for(int i=1; i<h; i++){
        for(int j=1; j<l; j++){

            for(int ii = 0; ii < 3; ii++){
                for(int jj = 0; jj < 3; jj++){
                    couleur = copy->pixel(jj + j -1, ii + i -1);

                    tableauRouge[ii*3 +jj]  = qRed(couleur);
                    tableauVert[ii*3 +jj]   = qGreen(couleur);
                    tableauBleu[ii*3 +jj]   = qBlue(couleur);
                    tableauAlpha[ii*3 +jj]  = qAlpha(couleur);
                }
            }

            // on prend la valeur mediane des tableaux
            coefTmpRouge    = Matrices::getMedianne(tableauRouge);
            coefTmpVert     = Matrices::getMedianne(tableauVert);
            coefTmpBleu     = Matrices::getMedianne(tableauBleu);
            coefTmpAlpha    = Matrices::getMedianne(tableauAlpha);

            image->setPixel(j, i, qRgba(coefTmpRouge, coefTmpVert, coefTmpBleu, coefTmpAlpha));
        }
    }
    delete copy;
}

int Matrices::getMedianne(int tableau[]){
    // on trie le tableau
    Matrices::triFusion(tableau, 9);

    // et on retourne la valeur situee au milieu
    return tableau[4];
}

void Matrices::fusion(int tableau[],const int debut1,const int fin1,const int fin2)
{
   int *tableau2;
   int debut2 = fin1+1;
   int compteur1 = debut1;
   int compteur2 = debut2;
   int i;

   tableau2 = (int*)malloc((fin1-debut1+1)*sizeof(int));

   // copie des éléments du début de tableau
   for(i=debut1; i<=fin1; i++)
      tableau2[i-debut1] = tableau[i];

   // fusion des deux tableaux
   for(i=debut1; i<=fin2; i++)
   {
      if(compteur1==debut2) // éléments du 1er tableau tous utilisés
         break; // éléments tous classés
      else if(compteur2==(fin2+1)) // éléments du 2nd tableau tous utilisés
      { // copie en fin de tableau des éléments du 1er sous tableau
         tableau[i] = tableau2[compteur1-debut1];
         compteur1++;
      }
      else if(tableau2[compteur1-debut1]<tableau[compteur2])
      { // ajout d'1 élément du 1er sous tableau
         tableau[i] = tableau2[compteur1-debut1];
         compteur1++; // on avance ds le 1er sous tableau
      }
      else
      { // copie de l'élément à la suite du tableau
         tableau[i] = tableau[compteur2];
         compteur2++; // on avance ds le 2nd sous tableau
      }
   }
   free(tableau2);
}

void Matrices::triFusionAux(int tableau[], const int debut, const int fin)
{
   if(debut!=fin) // condition d'arrêt
   {
      int milieu = (debut+fin)/2;
      triFusionAux(tableau, debut, milieu); // trie partie1
      triFusionAux(tableau, milieu+1, fin); // trie partie2
      fusion(tableau, debut, milieu, fin); // fusion des deux parties
   }
}

void Matrices::triFusion(int tableau[], const int longueur)
{
   if(longueur>0)
      triFusionAux(tableau, 0, longueur-1);
}

Matrices * Matrices::convolutionGrise(QImage * image, Matrices * noyau, double sommeCoef){
    // les rayons du noyeau
    int rayonHauteur    = (noyau->getHauteur() -1) /2;
    int rayonLargeur    = (noyau->getLargeur() -1) /2;
    // la normalisation
    QRgb couleur;
    int coefTmpGris;
    int tmp;

    // on arrive sur les derniers pixels valides
    int h   = image->height() - rayonHauteur;
    int l   = image->width() - rayonLargeur;
    Matrices * output = new Matrices(image->height(), image->width());

    // puis on boucle
    for(int i=rayonHauteur; i<h; i++){
        for(int j=rayonLargeur; j<l; j++){

            coefTmpGris     = 0;

            for(int ii = 0; ii < noyau->getHauteur(); ii++){
                for(int jj = 0; jj < noyau->getLargeur(); jj++){
                    couleur = image->pixel(jj + j - rayonLargeur, ii + i - rayonHauteur);
                    tmp     = noyau->getValeurDansCase(ii, jj);

                    coefTmpGris     += qRed(couleur) * tmp;
                }
            }

            coefTmpGris     = coefTmpGris/sommeCoef;

            output->setValeurDansCase(i, j, coefTmpGris);
        }
    }
    return output;
}

Matrices * Matrices::getNoyauGaussien(int tailleNoyau){
    if(tailleNoyau == 3){
        return Matrices::getNoyauGaussien3();
    }else
    if(tailleNoyau == 5){
        return Matrices::getNoyauGaussien5();
    }else
    if(tailleNoyau == 7){
        return Matrices::getNoyauGaussien7();
    }else
    if(tailleNoyau == 9){
        return Matrices::getNoyauGaussien9();
    }

    return Matrices::getNoyauGaussien3();
}

Matrices * Matrices::getNoyauGaussien3(){
    Matrices * gaussienne = new Matrices(3, 3);

    gaussienne->setValeurDansCase(0, 0, 1);
    gaussienne->setValeurDansCase(0, 1, 2);
    gaussienne->setValeurDansCase(0, 2, 1);
    gaussienne->setValeurDansCase(1, 0, 2);
    gaussienne->setValeurDansCase(1, 1, 4);
    gaussienne->setValeurDansCase(1, 2, 2);
    gaussienne->setValeurDansCase(2, 0, 1);
    gaussienne->setValeurDansCase(2, 1, 2);
    gaussienne->setValeurDansCase(2, 2, 1);

    return gaussienne;
}

Matrices * Matrices::getNoyauGaussien5(){
    Matrices * gaussienne = new Matrices(5, 5);

    gaussienne->setValeurDansCase(0, 0, 1);
    gaussienne->setValeurDansCase(0, 1, 4);
    gaussienne->setValeurDansCase(0, 2, 7);
    gaussienne->setValeurDansCase(0, 3, 4);
    gaussienne->setValeurDansCase(0, 4, 1);

    gaussienne->setValeurDansCase(1, 0, 4);
    gaussienne->setValeurDansCase(1, 1, 16);
    gaussienne->setValeurDansCase(1, 2, 26);
    gaussienne->setValeurDansCase(1, 3, 16);
    gaussienne->setValeurDansCase(1, 4, 4);

    gaussienne->setValeurDansCase(2, 0, 7);
    gaussienne->setValeurDansCase(2, 1, 26);
    gaussienne->setValeurDansCase(2, 2, 41);
    gaussienne->setValeurDansCase(2, 3, 26);
    gaussienne->setValeurDansCase(2, 4, 7);

    gaussienne->setValeurDansCase(3, 0, 4);
    gaussienne->setValeurDansCase(3, 1, 16);
    gaussienne->setValeurDansCase(3, 2, 26);
    gaussienne->setValeurDansCase(3, 3, 16);
    gaussienne->setValeurDansCase(3, 4, 4);

    gaussienne->setValeurDansCase(4, 0, 1);
    gaussienne->setValeurDansCase(4, 1, 4);
    gaussienne->setValeurDansCase(4, 2, 7);
    gaussienne->setValeurDansCase(4, 3, 4);
    gaussienne->setValeurDansCase(4, 4, 1);

    return gaussienne;
}


Matrices * Matrices::getNoyauGaussien7(){
    Matrices * gaussienne = new Matrices(7, 7);

    gaussienne->setValeurDansCase(0, 0, 1);
    gaussienne->setValeurDansCase(0, 1, 6);
    gaussienne->setValeurDansCase(0, 2, 15);
    gaussienne->setValeurDansCase(0, 3, 20);
    gaussienne->setValeurDansCase(0, 4, 15);
    gaussienne->setValeurDansCase(0, 5, 6);
    gaussienne->setValeurDansCase(0, 6, 1);

    gaussienne->setValeurDansCase(1, 0, 6);
    gaussienne->setValeurDansCase(1, 1, 36);
    gaussienne->setValeurDansCase(1, 2, 90);
    gaussienne->setValeurDansCase(1, 3, 120);
    gaussienne->setValeurDansCase(1, 4, 90);
    gaussienne->setValeurDansCase(1, 5, 36);
    gaussienne->setValeurDansCase(1, 6, 6);

    gaussienne->setValeurDansCase(2, 0, 15);
    gaussienne->setValeurDansCase(2, 1, 90);
    gaussienne->setValeurDansCase(2, 2, 225);
    gaussienne->setValeurDansCase(2, 3, 300);
    gaussienne->setValeurDansCase(2, 4, 225);
    gaussienne->setValeurDansCase(2, 5, 90);
    gaussienne->setValeurDansCase(2, 6, 15);

    gaussienne->setValeurDansCase(3, 0, 20);
    gaussienne->setValeurDansCase(3, 1, 120);
    gaussienne->setValeurDansCase(3, 2, 300);
    gaussienne->setValeurDansCase(3, 3, 400);
    gaussienne->setValeurDansCase(3, 4, 300);
    gaussienne->setValeurDansCase(3, 5, 120);
    gaussienne->setValeurDansCase(3, 6, 20);

    gaussienne->setValeurDansCase(4, 0, 15);
    gaussienne->setValeurDansCase(4, 1, 90);
    gaussienne->setValeurDansCase(4, 2, 225);
    gaussienne->setValeurDansCase(4, 3, 300);
    gaussienne->setValeurDansCase(4, 4, 225);
    gaussienne->setValeurDansCase(4, 5, 90);
    gaussienne->setValeurDansCase(4, 6, 15);

    gaussienne->setValeurDansCase(5, 0, 6);
    gaussienne->setValeurDansCase(5, 1, 36);
    gaussienne->setValeurDansCase(5, 2, 90);
    gaussienne->setValeurDansCase(5, 3, 120);
    gaussienne->setValeurDansCase(5, 4, 90);
    gaussienne->setValeurDansCase(5, 5, 36);
    gaussienne->setValeurDansCase(5, 6, 6);

    gaussienne->setValeurDansCase(6, 0, 1);
    gaussienne->setValeurDansCase(6, 1, 6);
    gaussienne->setValeurDansCase(6, 2, 15);
    gaussienne->setValeurDansCase(6, 3, 20);
    gaussienne->setValeurDansCase(6, 4, 15);
    gaussienne->setValeurDansCase(6, 5, 6);
    gaussienne->setValeurDansCase(6, 6, 1);

    return gaussienne;
}

Matrices * Matrices::getNoyauGaussien9(){
    Matrices * gaussienne = new Matrices(9, 9);

    gaussienne->setValeurDansCase(0, 0, 1);
    gaussienne->setValeurDansCase(0, 1, 8);
    gaussienne->setValeurDansCase(0, 2, 28);
    gaussienne->setValeurDansCase(0, 3, 56);
    gaussienne->setValeurDansCase(0, 4, 70);
    gaussienne->setValeurDansCase(0, 5, 56);
    gaussienne->setValeurDansCase(0, 6, 28);
    gaussienne->setValeurDansCase(0, 7, 8);
    gaussienne->setValeurDansCase(0, 8, 1);

    gaussienne->setValeurDansCase(1, 0, 8);
    gaussienne->setValeurDansCase(1, 1, 64);
    gaussienne->setValeurDansCase(1, 2, 224);
    gaussienne->setValeurDansCase(1, 3, 448);
    gaussienne->setValeurDansCase(1, 4, 560);
    gaussienne->setValeurDansCase(1, 5, 448);
    gaussienne->setValeurDansCase(1, 6, 224);
    gaussienne->setValeurDansCase(1, 7, 64);
    gaussienne->setValeurDansCase(1, 8, 8);

    gaussienne->setValeurDansCase(2, 0, 28);
    gaussienne->setValeurDansCase(2, 1, 224);
    gaussienne->setValeurDansCase(2, 2, 784);
    gaussienne->setValeurDansCase(2, 3, 1568);
    gaussienne->setValeurDansCase(2, 4, 1960);
    gaussienne->setValeurDansCase(2, 5, 1568);
    gaussienne->setValeurDansCase(2, 6, 784);
    gaussienne->setValeurDansCase(2, 7, 224);
    gaussienne->setValeurDansCase(2, 8, 28);

    gaussienne->setValeurDansCase(3, 0, 56);
    gaussienne->setValeurDansCase(3, 1, 448);
    gaussienne->setValeurDansCase(3, 2, 1568);
    gaussienne->setValeurDansCase(3, 3, 3136);
    gaussienne->setValeurDansCase(3, 4, 3920);
    gaussienne->setValeurDansCase(3, 5, 3136);
    gaussienne->setValeurDansCase(3, 6, 1568);
    gaussienne->setValeurDansCase(3, 7, 448);
    gaussienne->setValeurDansCase(3, 8, 56);

    gaussienne->setValeurDansCase(4, 0, 70);
    gaussienne->setValeurDansCase(4, 1, 560);
    gaussienne->setValeurDansCase(4, 2, 1960);
    gaussienne->setValeurDansCase(4, 3, 3920);
    gaussienne->setValeurDansCase(4, 4, 4900);
    gaussienne->setValeurDansCase(4, 5, 3920);
    gaussienne->setValeurDansCase(4, 6, 1960);
    gaussienne->setValeurDansCase(4, 7, 560);
    gaussienne->setValeurDansCase(4, 8, 70);

    gaussienne->setValeurDansCase(5, 0, 56);
    gaussienne->setValeurDansCase(5, 1, 448);
    gaussienne->setValeurDansCase(5, 2, 1568);
    gaussienne->setValeurDansCase(5, 3, 3136);
    gaussienne->setValeurDansCase(5, 4, 3920);
    gaussienne->setValeurDansCase(5, 5, 3136);
    gaussienne->setValeurDansCase(5, 6, 1568);
    gaussienne->setValeurDansCase(5, 7, 448);
    gaussienne->setValeurDansCase(5, 8, 56);

    gaussienne->setValeurDansCase(6, 0, 28);
    gaussienne->setValeurDansCase(6, 1, 224);
    gaussienne->setValeurDansCase(6, 2, 784);
    gaussienne->setValeurDansCase(6, 3, 1568);
    gaussienne->setValeurDansCase(6, 4, 1960);
    gaussienne->setValeurDansCase(6, 5, 1568);
    gaussienne->setValeurDansCase(6, 6, 784);
    gaussienne->setValeurDansCase(6, 7, 224);
    gaussienne->setValeurDansCase(6, 8, 28);

    gaussienne->setValeurDansCase(7, 0, 8);
    gaussienne->setValeurDansCase(7, 1, 64);
    gaussienne->setValeurDansCase(7, 2, 224);
    gaussienne->setValeurDansCase(7, 3, 448);
    gaussienne->setValeurDansCase(7, 4, 560);
    gaussienne->setValeurDansCase(7, 5, 448);
    gaussienne->setValeurDansCase(7, 6, 224);
    gaussienne->setValeurDansCase(7, 7, 64);
    gaussienne->setValeurDansCase(7, 8, 8);

    gaussienne->setValeurDansCase(8, 0, 1);
    gaussienne->setValeurDansCase(8, 1, 8);
    gaussienne->setValeurDansCase(8, 2, 28);
    gaussienne->setValeurDansCase(8, 3, 56);
    gaussienne->setValeurDansCase(8, 4, 70);
    gaussienne->setValeurDansCase(8, 5, 56);
    gaussienne->setValeurDansCase(8, 6, 28);
    gaussienne->setValeurDansCase(8, 7, 8);
    gaussienne->setValeurDansCase(8, 8, 1);

    return gaussienne;
}
Matrices * Matrices::getNoyauMoyenneCarreDeTaille(int taille){
    Matrices * moyenne  = new Matrices(taille, taille);

    moyenne->remplirMatriceDe(1);

    return moyenne;
}


Matrices * Matrices::getNoyauSobelKernelX(){
    Matrices * KernelX = new Matrices(3, 3);

    KernelX ->setValeurDansCase(0, 0, 1);
    KernelX ->setValeurDansCase(0, 1, 0);
    KernelX ->setValeurDansCase(0, 2, -1);
    KernelX ->setValeurDansCase(1, 0, 2);
    KernelX ->setValeurDansCase(1, 1, 0);
    KernelX ->setValeurDansCase(1, 2, -2);
    KernelX ->setValeurDansCase(2, 0, 1);
    KernelX ->setValeurDansCase(2, 1, 0);
    KernelX ->setValeurDansCase(2, 2, -1);

    return KernelX ;
}

Matrices * Matrices::getNoyauSobelKernelY(){
    Matrices * KernelY = new Matrices(3, 3);

    KernelY ->setValeurDansCase(0, 0, 1);
    KernelY ->setValeurDansCase(0, 1, 2);
    KernelY ->setValeurDansCase(0, 2, 1);
    KernelY ->setValeurDansCase(1, 0, 0);
    KernelY ->setValeurDansCase(1, 1, 0);
    KernelY ->setValeurDansCase(1, 2, 0);
    KernelY ->setValeurDansCase(2, 0, -1);
    KernelY ->setValeurDansCase(2, 1, -2);
    KernelY ->setValeurDansCase(2, 2, -1);

    return KernelY ;
}


Matrices * Matrices::getNoyauRobertsKernelX(){
    Matrices * KernelX = new Matrices(1, 3);

    KernelX ->setValeurDansCase(0, 0, 1);
    KernelX ->setValeurDansCase(0, 1, 0);
    KernelX ->setValeurDansCase(0, 2, -1);
    return KernelX ;
}

Matrices * Matrices::getNoyauRobertsKernelY(){
    Matrices * KernelY = new Matrices(3, 1);

    KernelY ->setValeurDansCase(0, 0, 1);
    KernelY ->setValeurDansCase(1, 0, 0);
    KernelY ->setValeurDansCase(2, 0, -1);

    return KernelY ;
}

Matrices * Matrices::image3Dto1D(QImage * image){
    Matrices * output   = new Matrices(image->height(), image->width());
    for(int i=0; i<image->height(); i++){
        for(int j=0; j<image->width(); j++){
            output->setValeurDansCase(i, j, qRed(image->pixel(j, i)));
        }
    }

    return output;
}

void Matrices::cheminVerticalDEnergieMinimale(QImage * image){
    int h   = image->height();
    int l   = image->width();

    // on prepare les structures servant aux calculs
    Matrices * poids            = new Matrices(h, l);
    Matrices * memoireChemins   = new Matrices(h-1, l);

    // puis on applique l'algorithme sur chaque colonne de chaque ligne
    // en traitent la premiere ligne en cas particulier
    for(int j=0; j<l; j++){
        poids->setValeurDansCase(0, j, 0);
    }

    int posPrec;

    for(int i=1; i<h; i++){

        // traitement premiere colonne
        if(poids->getValeurDansCase(i-1, 1) < poids->getValeurDansCase(i-1, 0)){
            posPrec = 1;
        }else{
            posPrec = 0;
        }
        poids->setValeurDansCase(i, 0, poids->getValeurDansCase(i-1, posPrec) + qRed(image->pixel(0, i))*qRed(image->pixel(0, i)));
        memoireChemins->setValeurDansCase(i-1, 0, posPrec);

        // traitement colonnes du milieu
        for(int j=1; j<l-1; j++){

            if(poids->getValeurDansCase(i-1, j-1) < poids->getValeurDansCase(i-1, j)){
                if(poids->getValeurDansCase(i-1, j-1) < poids->getValeurDansCase(i-1, j+1)){
                    posPrec = -1;
                }else{
                    posPrec = 1;
                }
            }else{
                if(poids->getValeurDansCase(i-1, j+1) < poids->getValeurDansCase(i-1, j)){
                    posPrec = 1;
                }else{
                    posPrec = 0;
                }
            }
            // on rajoute notre poids au poids minimal au dessus de nous
            poids->setValeurDansCase(i, j, poids->getValeurDansCase(i-1, j+posPrec) + qRed(image->pixel(j, i))*qRed(image->pixel(j, i)));
            memoireChemins->setValeurDansCase(i-1, j, posPrec);

        }

        // traitement derniere colonne
        if(poids->getValeurDansCase(i-1, l-2) < poids->getValeurDansCase(i-1, l-1)){
            posPrec = -1;
        }else{
            posPrec = 0;
        }
        poids->setValeurDansCase(i, l-1, poids->getValeurDansCase(i-1, l-1+posPrec) + qRed(image->pixel(l-1, i))*qRed(image->pixel(l-1, i)));
        memoireChemins->setValeurDansCase(i-1, l-1, posPrec);

    }
    // ici, nous avons calcule tous les chemins


    int minTmp      = poids->getValeurDansCase(h-1, 0);
    int indiceMin   = 0;
    for(int j=1; j<l; j++){
        if(poids->getValeurDansCase(h-1, j) < minTmp){
            minTmp      = poids->getValeurDansCase(h-1, j);
            indiceMin   = j;
        }
    }
    // on connait la colonne de plus faible valeur : indiceMin
    // on remonte le chemin
    for(int i=h-1; i>0; i--){
        image->setPixel(indiceMin, i, qRgb(255, 0, 0));

        // on redefini l'incide min
        indiceMin   = indiceMin + memoireChemins->getValeurDansCase(i-1, indiceMin);
    }
    image->setPixel(indiceMin, 0, qRgb(255, 0, 0));
}

void Matrices::cheminHorizontalDEnergieMinimale(QImage * image){
    int h   = image->height();
    int l   = image->width();

    // on prepare les structures servant aux calculs
    Matrices * poids            = new Matrices(h, l);
    Matrices * memoireChemins   = new Matrices(h, l-1);

    // puis on applique l'algorithme sur chaque colonne de chaque ligne
    // en traitent la premiere ligne en cas particulier
    for(int i=0; i<h; i++){
        poids->setValeurDansCase(i, 0, 0);
    }

    int posPrec;

    for(int j=1; j<l; j++){

        // traitement premiere colonne
        if(poids->getValeurDansCase(1, j-1) < poids->getValeurDansCase(0, j-1)){
            posPrec = 1;
        }else{
            posPrec = 0;
        }
        poids->setValeurDansCase(0, j, poids->getValeurDansCase(posPrec, j-1) + qRed(image->pixel(j, 0))*qRed(image->pixel(j, 0)));
        memoireChemins->setValeurDansCase(0, j-1, posPrec);

        // traitement colonnes du milieu
        for(int i=1; i<h-1; i++){

            if(poids->getValeurDansCase(i-1, j-1) < poids->getValeurDansCase(i, j-1)){
                if(poids->getValeurDansCase(i-1, j-1) < poids->getValeurDansCase(i+1, j-1)){
                    posPrec = -1;
                }else{
                    posPrec = 1;
                }
            }else{
                if(poids->getValeurDansCase(i+1, j-1) < poids->getValeurDansCase(i, j-1)){
                    posPrec = 1;
                }else{
                    posPrec = 0;
                }
            }
            // on rajoute notre poids au poids minimal au dessus de nous
            poids->setValeurDansCase(i, j, poids->getValeurDansCase(i+posPrec, j-1) + qRed(image->pixel(j, i))*qRed(image->pixel(j, i)));
            memoireChemins->setValeurDansCase(i, j-1, posPrec);

        }

        // traitement derniere colonne
        if(poids->getValeurDansCase(h-2, j-1) < poids->getValeurDansCase(h-1, j-1)){
            posPrec = -1;
        }else{
            posPrec = 0;
        }
        poids->setValeurDansCase(h-1, j, poids->getValeurDansCase(h-1+posPrec, j-1) + qRed(image->pixel(j, h-1))*qRed(image->pixel(j, h-1)));
        memoireChemins->setValeurDansCase(h-1, j-1, posPrec);

    }
    // ici, nous avons calcule tous les chemins


    int minTmp      = poids->getValeurDansCase(0, l-1);
    int indiceMin   = 0;
    for(int i=1; i<h; i++){
        if(poids->getValeurDansCase(i, l-1) < minTmp){
            minTmp      = poids->getValeurDansCase(i, l-1);
            indiceMin   = i;
        }
    }
    // on connait la colonne de plus faible valeur : indiceMin
    // on remonte le chemin
    for(int j=l-1; j>0; j--){
        image->setPixel(j, indiceMin, qRgb(255, 0, 0));

        // on redefini l'incide min
        indiceMin   = indiceMin + memoireChemins->getValeurDansCase(indiceMin, j-1);
    }
    image->setPixel(0, indiceMin, qRgb(255, 0, 0));
}
